#!/usr/bin/python3
# -*- coding: UTF-8 -*-
def insertion_sort(arr):
    """
    插入排序
    时间复杂度：O(n^2)
    空间复杂度：O(1)
    稳定性：稳定
    工作原理：
        从第二个元素开始：假设第一个元素已经排序。
        逐个向前插入：将当前元素与已排序部分的元素进行比较，并将其插入到正确的位置。
        重复步骤：重复上述过程，直到所有元素都被插入到正确的位置。
    优化：
        1. 二分查找插入位置
        2. 希尔排序
    :param arr:
    :return:
    """
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            else:
                break
    return arr

def optimized_insertion_sort(arr):
    """
    插入排序
    时间复杂度：O(n^2)
    空间复杂度：O(1)
    稳定性：稳定
    工作原理：
        从第二个元素开始：假设第一个元素已经排序。
        逐个向前插入：将当前元素与已排序部分的元素进行比较，并将其插入到正确的位置。
        重复步骤：重复上述过程，直到所有元素都被插入到正确的位置。
    优化：
        1. 二分查找插入位置
        2. 希尔排序
    :param arr: 需要排序的列表
    :return: 排序后的列表
    """
    # 检查输入是否为列表或其他可迭代对象
    if not isinstance(arr, (list, tuple)):
        raise TypeError("输入必须是列表或元组")

    # 处理边界条件
    if len(arr) <= 1:
        return arr

    # 插入排序
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

    return arr

